Communication with Contextual Uncertainty

摘要

We introduce a simple model illustrating the role of context in communicationand the challenge posed by uncertainty of knowledge of context. We consider avariant of distributional communication complexity where Alice gets someinformation $x$ and Bob gets $y$, where $(x,y)$ is drawn from a knowndistribution, and Bob wishes to compute some function $g(x,y)$ (with highprobability over $(x,y)$). In our variant, Alice does not know $g$, but onlyknows some function $f$ which is an approximation of $g$. Thus, the functionbeing computed forms the context for the communication, and knowing itimperfectly models (mild) uncertainty in this context. A naive solution would be for Alice and Bob to first agree on some commonfunction $h$ that is close to both $f$ and $g$ and then use a protocol for $h$to compute $h(x,y)$. We show that any such agreement leads to a large overheadin communication ruling out such a universal solution. In contrast, we show that if $g$ has a one-way communication protocol withcomplexity $k$ in the standard setting, then it has a communication protocolwith complexity $O(k \cdot (1+I))$ in the uncertain setting, where $I$ denotesthe mutual information between $x$ and $y$. In the particular case where theinput distribution is a product distribution, the protocol in the uncertainsetting only incurs a constant factor blow-up in communication and error. Furthermore, we show that the dependence on the mutual information $I$ isrequired. Namely, we construct a class of functions along with a non-productdistribution over $(x,y)$ for which the communication complexity is a singlebit in the standard setting but at least $\Omega(\sqrt{n})$ bits in theuncertain setting.